package fun.coding.geeksforgeeks;

import java.util.HashMap;
import java.util.Map;

public class MaximumProductCutting {

	public static void main(String[] args) {
		MaximumProductCutting ins = new MaximumProductCutting();
		System.out.println(ins.maxProduct(5));
		System.out.println(ins.maxProduct(10));
	}
	/**
	 * http://www.geeksforgeeks.org/dynamic-programming-set-36-cut-a-rope-to-maximize-product/
	 * Given a rope of length n meters, cut the rope in different parts of 
	 * integer lengths in a way that maximizes product of lengths of all parts.
	 * Input: n = 2 Output: 1 (Maximum obtainable product is 1*1)
	 * Input: n = 5 Output: 6 (Maximum obtainable product is 2*3)
	 */
	
	// DP solution with O(N^2)
	public int maxProduct(int n) {
		if (n <= 0)  return 0;
		
		int[] lookup = new int[n + 1];
		lookup[1] = 1;
		lookup[2] = 1;
		
		for (int i = 3; i <= n; i++) {
			int max = Integer.MIN_VALUE;
			for (int j = 1; j <= i / 2; j++) {
				max = Math.max(max, Math.max(j * (i - j), j * lookup[i - j]));
			}
			lookup[i] = max;
		}
		return lookup[n];
	}
	
	
	// Recursion with map pruning
	public int maxProductWithMap(int n) {
		if (n <= 0)  return 0;
		Map<Integer, Integer> lookup = new HashMap<Integer, Integer>();
		lookup.put(1, 1);
		lookup.put(2, 1);
		return helperWithMap(n, lookup);
	}
	
	private int helperWithMap(int n, Map<Integer, Integer> lookup) {
		if (lookup.containsKey(n)) return lookup.get(n);
		
		int max = Integer.MIN_VALUE;
		for (int i = 1; i < n; i++) {
			max = Math.max(max, Math.max(i * (n-i), i * helper(n-i)));
		}
		lookup.put(n, max);
		return max;
	}
	
	// Basic recursion
	public int maxProductRecursion(int n) {
		if (n <= 0)  return 0;
		
		return helper(n);
	}
	
	private int helper(int n) {
		if (n == 1) return 1;
		if (n == 2) return 1;
		
		int max = Integer.MIN_VALUE;
		for (int i = 1; i < n; i++) {
			max = Math.max(max, Math.max(i * (n-i), i * helper(n-i)));
		}
		
		return max;
	}
}
